// build by WuQilong at 2024/3/19
import java.util.Arrays;
import java.util.Objects;
import java.util.Scanner;

public class Wu_3_19 {
    public static void main(String[] args) {
        double[] array =new double[10];
        for (int i=0;i< array.length;i++){
            array[i]=(int)(Math.random()*100);
        }
        Scanner sc=new Scanner(System.in);
        System.out.print("please input the function which you want to call:");
        String name=sc.nextLine();
        System.out.println("before sorting"+Arrays.toString(array));
        if(Objects.equals(name, "mergesort")){
            //call mergesort
            System.out.println("start to call mergesort");
            new Wu_3_19().mergesort(array);
        } else if (Objects.equals(name,"quicksort")) {
            //call quicksort
            System.out.println("start to call quicksort");
            new Wu_3_19().quicksort(array,0, array.length-1);
        } else if (Objects.equals(name,"heapsort")){
            //call heapsort
            System.out.print("ascend or descend:");
            String n=sc.nextLine();
            if(Objects.equals(n, "ascend")){
                System.out.println("start to call heapsort");
                new Wu_3_19().heapsort_ascend(array);
            } else if (Objects.equals(n, "descend")) {
                System.out.println("start to call heapsort");
                new Wu_3_19().heapsort_descend(array);
            } else {
                System.out.println("error,please select from ascend and descend!");
            }
        }else{
            System.out.println("error,please input correct function!");
        }

        System.out.println("after sorting"+Arrays.toString(array));

    }
    void mergesort(double [] array){
        int length=array.length;
        //finish the recursion
        if(length<=1) return;
        int leftLength=length/2,rightLength=length-leftLength;
        double [] leftArray=new double[leftLength];
        double [] rightArray=new double[rightLength];
        //divide the array
        int j=0;
        for(int i=0;i<length;i++){
            if(i<leftLength){
                leftArray[i]=array[i];
            }
            else{
                rightArray[j++]=array[i];
            }
        }
        mergesort(leftArray);
        mergesort(rightArray);
        merge(leftArray,rightArray,array);
    }
    void merge(double [] leftArray,double [] rightArray,double [] array){
        int i=0,j=0,a=0;
        while(i<leftArray.length && j<rightArray.length){
            if(leftArray[i]<rightArray[j]){
                array[a]=leftArray[i];
                i++;a++;
            }else{
                array[a]=rightArray[j];
                j++;a++;
            }
        }
        // cope redundant element
        while(i< leftArray.length){
            array[a]=leftArray[i];
            i++;a++;
        }
        while(j<rightArray.length){
            array[a]=rightArray[j];
            j++;a++;
        }
    }
    void quicksort(double [] array,int low,int high){
        if(low>=high) return;
        int i=low ,j=high;
        //select a base
        double base =array[low];
        while(i<j){
            while(array[j]>=base && i<j)
                j--;
            while(array[i]<=base && i<j)
                i++;
            swap(array,i,j);
        }
        swap(array,low,j);
        quicksort(array,low,j-1);
        quicksort(array,j+1,high);
    }
    // maxHeapify  will ascend the array
    void heapsort_ascend(double [] array){
        buildMaxheap(array);
        for(int i= array.length-1;i>=1;i--){
            swap(array,0,i);
            maxHeapify(array,i,0);
        }
    }
    // int n will help us reduce the length of array easily
    // the precondition of the maxHeapify is its all subHeap are maxHeap
    void maxHeapify(double [] array,int n,int i){
        int l=2*i+1,r=2*(i+1);
        int max=i;
        if(l<n && array[i]<array[l])
            max=l;
        if(r<n && array[max]<array[r])
            max=r;
        // this is so important that if the position of max change,call maxHeapify(),else loop ceaselessly
        if(max!=i){
            swap(array,i,max);
            maxHeapify(array,n,max);
        }
    }
    void buildMaxheap(double [] array){
        //为了减少计算量，array.length/2-1 是最小开始构建堆的元素位置
        //当然从最后一个元素开始构建也可以，但是效率极低，做了一半无效计算
        for(int i=array.length/2-1;i>=0;i--)
            maxHeapify(array,array.length,i);
    }

    void heapsort_descend(double [] array){
        buildMinheap(array);
        for(int i=array.length-1;i>=1;i--){
            swap(array,0,i);
            minHeapify(array,i,0);
        }
    }
    void minHeapify(double[] array,int n,int i){
        int l=2*i+1,r=2*(i+1);
        int min=i;
        if(l<n && array[i]>array[l])
            min=l;
        if(r<n && array[min]>array[r])
            min=r;
        // this is so important that if the position of max change,call maxHeapify(),else loop ceaselessly
        if(min!=i){
            swap(array,i,min);
            minHeapify(array,n,min);
        }
    }
    void buildMinheap(double [] array){
        for(int i=(array.length-1)/2;i>=0;i--)
            minHeapify(array,array.length,i);
    }
    void swap(double[]array,int i,int j){
        double temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }
}
